#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
using i64 = long long;

ll n;

ll val(ll i, ll j) { return (i - 1) * n + j; }

i64 gcd(i64 a, i64 b)
{
    return b ? gcd(b, a % b) : a;
}

void solve()
{
    i64 a, b;
    cin >> a >> b;
    if (a == 1) {
        if (b == 1) {
            cout << "-1" << '\n';
        }
        else {
            cout << b << '\n';
        }
        return;
    }
    i64 d = gcd(a, b);
    //cout<<"fdsgffdg" << gcd(172635817456, 237896190123) << endl;
    i64 x = b / d;
    // if (x == b) {
    //     cout << "-1" << '\n';
    //     return;
    // }
    while (gcd(a, x)>1 && x > 1) {
        x /= gcd(a, x);
    }
    if (x == 1) {
        cout << "-1" << '\n';
    }
    else {
        cout << x << '\n';
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
#define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
    std::istringstream in(R"()");
    std::cin.rdbuf(in.rdbuf());
#endif
    ll T = 1;
    cin >> T;
    for (ll i = 1;i <= T;i++) {
        solve();
    }
}